﻿//非递归的快排，用栈实现，因为栈的功能与递归相似，但有所不同
//#include <assert.h>
//#include <stdlib.h>
//#include <stdio.h>
//typedef struct stack {
//	int* Data;
//	int Capacity;
//	int Top;
//}Stack;
//void StackInit(Stack* S);
//void StackPop(Stack* S);
//void StackPush(Stack* S, int X);
//
//void StackInit(Stack* S) {
//	assert(S);
//	S->Data = 0;
//	S->Capacity = 0;
//	S->Top = -1;
//}
//void StackPop(Stack* S) {
//	assert(S || S->Data || S->Top != -1);
//	S->Top--;
//}
//void StackPush(Stack* S, int X) {
//	assert(S);
//	if (!S->Data) {
//		S->Data = (int*)malloc(sizeof(int) * 4);
//		assert(S->Data);
//		S->Capacity = 4;
//	}
//	else if (S->Top == S->Capacity - 1) {
//		S->Data = (int*)realloc(S->Data, (sizeof(int) * S->Capacity) * 2);
//		assert(S->Data);
//		S->Capacity *= 2;
//	}
//	S->Data[++S->Top] = X;
//}
//void QuickSort(int* a, int left, int right) {
//	Stack* S = (Stack*)malloc(sizeof(Stack));
//	StackInit(S);
//	StackPush(S, right);
//	StackPush(S, left);
//	while (S->Top != -1) {
//		//确定左右区间
//		int begin = S->Data[S->Top];
//		StackPop(S);
//		int end = S->Data[S->Top];
//		StackPop(S);
//		//用指定好的区间进行预排序，即一次遍历
//		int key = PartSort1(a, begin, end);
//		//进行左区间的遍历
//		if (end - 1 > begin) {
//			StackPush(S, end - 1);
//			StackPush(S, begin);
//		}
//		//进行右区间的遍历
//		if (begin + 1 < end) {
//			StackPush(S, end);
//			StackPush(S, begin + 1);
//		}
//	}
//	free(S);
//	//注意，不能在此算法内这样写，因为这是的a是首元素地址，即指针，sizeof(a)为地址的大小
//	//Print(a, sizeof(a) / sizeof(int));
//}
//int main() {
//	int a[] = { 0,5,7,9,3,4,1,6,2,8 };
//	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
//	Print(a, sizeof(a) / sizeof(int));
//	return 0;
//}